class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        left_stack = [root]
        right_stack = [root]
        while left_stack[-1].left:
            left_stack.append(left_stack[-1].left)
        while right_stack[-1].right:
            right_stack.append(right_stack[-1].right)
        while left_stack[-1].val != right_stack[-1].val:
            node1 = left_stack[-1]
            node2 = right_stack[-1]
            if node1.val + node2.val == k:
                return True
            if node1.val + node2.val < k:
                left_stack.pop()
                if node1.right:
                    node1 = node1.right
                    while node1:
                        left_stack.append(node1)
                        node1 = node1.left
            else:
                right_stack.pop()
                if node2.left:
                    node2 = node2.left
                    while node2:
                        right_stack.append(node2)
                        node2 = node2.right
        return False
